This invention relates to the reclamation of unused memory space, or “garbage collection”, using space-incremental collection techniques. Memory reclamation may be carried out by a special purpose garbage collection algorithm that locates and reclaims memory which is unused, but has not been explicitly de-allocated. There are many known garbage collection algorithms, including reference counting, mark-sweep, mark-compaction and generational garbage collection algorithms. These, and other garbage collection techniques, are described in detail in a book entitled “Garbage Collection, Algorithms For Automatic Dynamic Memory Management” by Richard Jones and Raphael Lins, John Wiley & Sons, 1996.
However, many of the aforementioned garbage collection techniques often lead to long and unpredictable delays because normal processing must be suspended during the garbage collection process. Therefore, they are generally not suitable in situations, such as real-time or interactive systems, where non-disruptive behavior is of greatest importance. Conventional generational collection techniques alleviate these delays somewhat by concentrating collection efforts on small memory areas, called “young” generations in which most of the activity occurs. This concentration reduces the need for collecting the remaining large memory area, called the “old” or “mature” generation and, thus, reduces the time consumed during garbage collection.
When the mature generation is eventually collected, many generational techniques lead to pauses in normal operation which, while less frequent, are still highly disruptive. One approach to eliminate these long pauses is to apply a space-incremental technique to the regions containing older objects. Space-incremental collection techniques allow a subset of objects in the heap to be collected and evacuated independently of the rest of the heap. A given subset consists of one or more possibly noncontiguous regions and forms the collection-set. Examples of such techniques include the Train algorithm as described in “Incremental Collection of Mature Objects”, R. L. Hudson, J. E. B. Moss, Proceedings of the International Workshop on Memory Management, volume 637 of Lecture Notes in Computer Science, St. Malo, France, pp 388-403, 1992, Springer-Verlag, London, Great Britain; the Garbage-first algorithm as described in “Garbage-First Garbage Collection”, D. Detlefs, C. Flood, S. Heller, A. Printezis, Proceedings of the 4th International Symposium on Memory Management, pp 37-48, 2004 and other techniques allowing partial compaction of the heap as described in “An Algorithm for Parallel Incremental Compaction”, O. Ben-Yitzhak, I. Goft, E. K. Kolodner, K. Kuiper, V. Leikehman, Proceedings of the 3rd International Symposium on Memory Management, pp 100-105, 2002.
As an example, the Train algorithm divides the generation's memory into a number of fixed-sized regions, or car sections. The algorithm associates a car structure with each car section to manage information about the state of that car section. It further orders the car structures in a two-level ordering. During at least some of the collection pauses, one or more of the cars lowest in the overall order are collected; these form the collection-set. Using this ordering and careful placement policies, the algorithm allows the size of collection-sets to be bounded to achieve acceptable pause times even as it guarantees that unreachable data structures too large to fit into a collection-set will be isolated in single trains, and once there, reclaimed as a group.
During the operation of the algorithm, objects in a car may be evacuated, or relocated, to other cars. Incremental collectors, such as the Train algorithm, are attractive because they do not introduce significant delays in the collection process. In addition, they are suitable for concurrent garbage collection systems in which collection is performed in parallel by several concurrent threads or by different processors in a multiprocessor system. However, since the Train algorithm relocates most objects by copying them to new locations during a collection, traditionally all application threads are suspended during the collection process.
In order to allow the collection process to take place while non-collection threads are running, it is important to ensure that the algorithm does not mutilate the objects during the collection process in a manner visible to the non-collection threads. For example, if forwarding pointers are installed for relocated objects, these installed pointers cannot obliterate data that the non-collection threads will need.
Conventional solutions to prevent object mutilation have employed read barriers, which intercept an attempted read to data in the collected space and cause the read to be made through a forwarding pointer to obtain the relocated data. Alternatively, other solutions use non-destructive copying to relocate objects. Since the original object remains intact until the copying is complete, the relocation does not mutilate the object. When the copying is complete, the collector replaces the appropriate non-collection thread register contents and stack locations with pointers to the relocated copies. For example, non-destructive copying can be used with the Train algorithm to evacuate an object from a car by copying the object to another car and then updating references to the object to reflect its new location at the time memory associated with the car is reclaimed. In order to insure that the copying is non-destructive, these solutions must store the forwarding address and typically allocate space for this purpose in object headers.
Unfortunately, these conventional solutions consume additional space per object. For example, if the average object is 8-10 words in size, adding a word to the header of each object increases the average object size by 10-12.5%.